package com.awakening.sorting.basic;

import com.awakening.sorting.util.JavaLikeSwap;
import com.awakening.sorting.util.SortTestHelper;

/**
 * 基本插入算法
 * @Author:AwakeningCode
 * @Date: Created in 11:09 2018\1\17 0017
 */
public class InsertionSort {

    //InsertionSort算法类不允许产生任何实例
    private InsertionSort(){}

    public static void sort(Comparable[] arr){
        int n = arr.length;
        // 寻找元素arr[i]合适的插入位置
        for (int i = 0; i < n ; i ++){
            // 写法1
//            for( int j = i ; j > 0 ; j -- )
//                if( arr[j].compareTo( arr[j-1] ) < 0 )
//                    swap( arr, j , j-1 );
//                else
//                    break;

            // 写法2
            for (int j = i ; j > 0 && arr[j].compareTo(arr[j-1]) < 0 ; j --){
                //置换数据比对比数据更耗性能
                JavaLikeSwap.swapComparable(arr,j,j-1);
                //尽可能改变插入算法，让它在内层循环中只交换一次，并且提前终止内层循环，提高性能
            }
        }
    }

    //测试InsertionSort
    public static void main(String[] args) {
        int N = 20000;
        Integer[] arr = SortTestHelper.generateRandomArray(N,0,10000);
        SortTestHelper.testSort("com.awakening.sorting.basic.InsertionSort",arr);
        return;
    }
}
